package com.data.structure.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 哈夫曼树
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/7/20
 */
public class HuffmanTree {


    public static void main(String[] args) {
        int arr[] = {2,3,7,9,18,25};
        Node root = createHuffmanTree(arr);
        preOrder(root);
    }
    /**
     * 前序遍历
     * @param root
     */
    public static void preOrder(Node root){
        if (null != root){
            root.preOrder();
        }else {
            System.out.println("该树为空！");
        }
    }

    /**
     * 构建哈夫曼树
     * @param arr
     * @return
     */
    public static Node createHuffmanTree(int[] arr){
        List<Node> nodes = new ArrayList<>();

        for(int value : arr){
            nodes.add(new Node(value));
        }

        while ((nodes.size() > 1)){
            Collections.sort(nodes);

            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);

            Node parent = new Node(leftNode.value+rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;

            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}
